package com.tyrone.algorithm.symbol;

/**
 * 有序符号表
 * @param <Key>
 * @param <Value>
 */
public class OrderSymbolTable<Key extends Comparable<Key>,Value> {
    //记录首结点
    private Node head;
    //记录符号表中键值对的个数
    private int N;

    public OrderSymbolTable() {
        this.head = new Node(null,null,null);
        N = 0;
    }

    /**
     * 根据键key，找对应的值
     * @param key
     * @return
     */
    public Value get(Key key){
        Node node = head;
        while(node.next!=null){
            node=node.next;
            if (node.key.equals(key)){
                return node.value;
            }
        }
        return null;
    }

    /**
     * 向符号表中插入一个键值对
     * @param key
     * @param val
     */
    public void put(Key key,Value val){
        Node pre  = head;
        Node curr = head.next;
        while (curr!=null&&key.compareTo(curr.key)>0){
            pre=curr;
            curr=curr.next;
        }
        if (curr!=null&&curr.key.compareTo(key)==0){
            curr.value=val;
            return;
        }
        Node node = new Node(key, val, curr);
        pre.next=node;
        N++;
    }

    /**
     * 删除键为key的键值对
     * @param key
     */
    public void delete(Key key){
        Node node = head;
        while (node.next!=null){
            if (node.next.key.equals(key)){
                node.next=node.next.next;
                N--;
                return;
            }
            node=node.next;
        }
    }

    /**
     * 获取符号表的大小
     * @return
     */
    public int size(){
        return N;
    }

    /**
     * 结点类
     */
    private class Node{
        private Key key;
        private Value value;
        public Node next;
        public Node(Key key, Value value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }
}
